Batch 3 - Class 169 - Grape Codes (Binary)

Pre-Class Exercise

(Dudeney - 98) There is a defective scale, due to unequal length of two arms, which shows the same weight with eight packets on right and three cans on left, as well as with one packet on left and six cans on right. If the true weight of a can is one ounce, how much does the packet weigh?

Answer: 8 x (weight of can) x (distance) = 3, and (weight of can) = 6 x (distance). This gives weight of can as 3/2. [Note that distance is really the ratio of two distances]

Attendance Smiti, Muskaan, Kushagra, Anishka, Arnav, Siddhanth, Damini, Arjun, Anshi, Liza, Ashvi

Class puzzles

Consider a row of dishes extending to as far left out as desired. We put grapes in the dishes, and total the numbers under it

There are 114 codes for number 26. Which is the code that uses least number of grapes? Which is the code that uses most number of grapes? How do you know?
Are there two different codes that use the same number of grapes? Are there 5 different codes that use the same number of grapes?

Note that 2,4,8,16 are separated by 2,3,4 numbers. Another way to see this is that there are [Sum of n natural numbers] numbers till nth bin (largest number represented being 2^n).
So, till 9th bin, we can get 45 numbers, the 45th number being 512. Then using the 10th bin, the 5th number now is 512+16=528

Now what are all the grape codes for number 7? Can you derive these from codes for number 6? Is it always true that codes for odd numbers are the same as codes for the even number that comes before? Why?

This is true, because there is only one bin which is an odd number, so odd numbers must have the first bin full. Rest of the grapes can be placed just like previous even number

Is it also true that codes for any even number can be derived from the prior odd number's codes?

Following is a series of codes for some initial even numbers. Can you guess the next three numbers?

Can you try and breakdown B(N), which means number of codes for N, where N is even? How many grapes must exist on rightmost bin - either 0 or 2+
0 case corresponds to B(N/2)
If we remove 2 from the 2+ case, then it is all representations of B(N-2). See this below for B(12), where the blue labels correspond to 2+ cases, and purple to 0 case.

Binary Codes - Any grape code with at most one grape in each bin is called a binary code.

List all grape codes for number 6. Which of these is its binary code? Is the binary code unique, can you prove it? Does it always exist?

It seems that the uniqueness can be proved intuitively. Assume that N is the smallest number which has two distinct binary code. There can't be an overlapping "1" in any place, because otherwise we can remove that "1" and arrive at a smaller number with two binary codes. Similarly, the rightmost digit in both can't be zero, otherwise we can divide the number by 2, and get to a smaller number with two binary codes. So one of the codes has rightmost digit 1 and other has 0, which means one representation is even and the other is odd, so both can't represent the same number.

Homework Problem:

(Dudeney - 373) During a country ramble Mr. and Mrs. Softleigh found themselves in a pretty little dilemma. They had to cross a stream in a small boat which was capable of carrying only 150 lbs. weight. But Mr. Softleigh and his wife each weighed exactly 150 lbs., and each of their sons weighed 75 lbs. And then there was the dog, who could not be induced on any terms to swim. On the principle of "ladies first," they at once sent Mrs. Softleigh over; but this was a stupid oversight, because she had to come back again with the boat, so nothing was gained by that operation. How did they all succeed in getting across? The reader will find it much easier than the Softleigh family did, for their greatest enemy could not have truthfully called them a brilliant quartette—while the dog was a perfect fool.

Answer: Sons cross together. One comes back, Father goes, other son comes back. Now again both sons go, one comes back, mother goes, other son come back. Now again, both sons go, and one comes back to get the dog.

References:

536 Puzzles and Curious Problems, Henry Dudeney